package com.shm.leetcode;

/**
 * 304. 二维区域和检索 - 矩阵不可变
 * 给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。
 *
 * Range Sum Query 2D
 * 上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。
 *
 * 示例:
 *
 * 给定 matrix = [
 *   [3, 0, 1, 4, 2],
 *   [5, 6, 3, 2, 1],
 *   [1, 2, 0, 1, 5],
 *   [4, 1, 0, 1, 7],
 *   [1, 0, 3, 0, 5]
 * ]
 *
 * sumRegion(2, 1, 4, 3) -> 8
 * sumRegion(1, 1, 2, 2) -> 11
 * sumRegion(1, 2, 2, 4) -> 12
 * 说明:
 *
 * 你可以假设矩阵不可变。
 * 会多次调用 sumRegion 方法。
 * 你可以假设 row1 ≤ row2 且 col1 ≤ col2。
 */
class NumMatrix {
    int[][] matrix;
//    public NumMatrix(int[][] matrix) {
//        this.matrix=matrix;
//    }
//
//    public int sumRegion(int row1, int col1, int row2, int col2) {
//        int ans = 0;
//        for(int i=row1;i<=row2;i++){
//            for(int j=col1;j<=col2;j++){
//                ans+=matrix[i][j];
//            }
//        }
//        return ans;
//    }


    int[][] sums;

    /**
     * 前言
     * 这道题是「303. 区域和检索 - 数组不可变」的进阶，第 303 题是在一维数组中做区域和检索，这道题是在二维矩阵中做区域和检索。
     *
     * 这道题有两种解法，分别是对每一行计算一维前缀和，以及对整个矩阵计算二维前缀和。
     *
     * 方法一：一维前缀和
     * 第 303 题中，初始化时对数组计算前缀和，每次检索即可在 O(1)O(1) 的时间内得到结果。可以将第 303 题的做法应用于这道题，初始化时对矩阵的每一行计算前缀和，检索时对二维区域中的每一行计算子数组和，然后对每一行的子数组和计算总和。
     *
     * 具体实现方面，创建 mm 行 n+1n+1 列的二维数组 \textit{sums}sums，其中 mm 和 nn 分别是矩阵 \textit{matrix}matrix 的行数和列数，\textit{sums}[i]sums[i] 为 \textit{matrix}[i]matrix[i] 的前缀和数组。将 \textit{sums}sums 的列数设为 n+1n+1 的目的是为了方便计算每一行的子数组和，不需要对 \textit{col}_1=0col
     * 1
     * ​
     *  =0 的情况特殊处理。
     *  复杂度分析
     *
     * 时间复杂度：初始化 O(mn)O(mn)，每次检索 O(m)O(m)，其中 mm 和 nn 分别是矩阵 \textit{matrix}matrix 的行数和列数。
     * 初始化需要遍历矩阵 \textit{matrix}matrix 计算二维前缀和，时间复杂度是 O(mn)O(mn)。
     * 每次检索需要对二维区域中的每一行计算子数组和，二维区域的行数不超过 mm，计算每一行的子数组和的时间复杂度是 O(1)O(1)，因此每次检索的时间复杂度是 O(m)O(m)。
     *
     * 空间复杂度：O(mn)O(mn)，其中 mm 和 nn 分别是矩阵 \textit{matrix}matrix 的行数和列数。需要创建一个 mm 行 n+1n+1 列的前缀和数组 \textit{sums}sums。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/range-sum-query-2d-immutable/solution/er-wei-qu-yu-he-jian-suo-ju-zhen-bu-ke-b-2z5n/
     * @param matrix
     */
    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        if(m>0){
            int n = matrix[0].length;
            sums = new int[m][n+1];
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    sums[i][j+1] = sums[i][j]+matrix[i][j];
                }
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int ans = 0;
        for(int i=row1;i<=row2;i++){
            ans+=(sums[i][col2+1]-sums[i][col1]);
        }
        return ans;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */